package hot100;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution23 {
    public ListNode mergeKLists(ListNode[] lists) {
        Queue<ListNode> queue = new LinkedList<>(Arrays.asList(lists));
        while (!queue.isEmpty() && queue.size() > 1) {
            int size = queue.size();
            for (int i = 0; i < size; i += 2) {
                queue.offer(mergeList(queue.poll(), queue.poll()));
            }
        }
        return queue.poll();
    }

    public ListNode mergeList(ListNode pHead, ListNode qHead) {
        ListNode head = new ListNode();
        ListNode node = head;
        while (pHead != null && qHead != null) {
            if (pHead.val > qHead.val) {
                node.next = qHead;
                qHead = qHead.next;
            } else {
                node.next = pHead;
                pHead = pHead.next;
            }
            node = node.next;
        }
        if (pHead != null) {
            node.next = pHead;
        } else {
            node.next = qHead;
        }
        return head.next;
    }

    public static void main(String[] args) {
        ListNode head1 = new ListNode(1);
        ListNode node = head1;
        node.next = new ListNode(4);
        node = node.next;
        node.next = new ListNode(5);
        ListNode head2 = new ListNode(1);
        node = head2;
        node.next = new ListNode(3);
        node = node.next;
        node.next = new ListNode(4);
        Solution23 solution23 = new Solution23();
        ListNode listNode = solution23.mergeList(head1, head2);

    }
}
